class Solution {
    //回溯法
    //难点在于对带*的特殊情况的判断
	//该方法为剑指offer书上做法，但时间复杂度过高并未通过
	//未通过项："aaaaaaaaaaaaab"，"a*a*a*a*a*a*a*a*a*a*c"
public:
    bool isMatch(string s, string p) {
        int sptr = 0;
        int pptr = 0;

        return matchCore(s, p, sptr, pptr);
    }


    bool matchCore(string &s, string &p, int sptr, int pptr){
        if(s[sptr] == '\0' && p[pptr] == '\0')  return true;
        if(s[sptr] != '\0' && p[pptr] == '\0')  return false;

        if(p[pptr + 1] == '*'){
            if(s[sptr] == p[pptr] || (p[pptr] == '.' && s[sptr] != '\0'))
                return matchCore(s, p, sptr + 1, pptr)//仍然接着匹配当前内容
                || matchCore(s, p, sptr + 1, pptr + 2)//接着匹配p的下一部分内容
                || matchCore(s, p, sptr, pptr + 2);//.*可能会匹配空串
            else
                return matchCore(s, p, sptr, pptr + 2);//该处字母+*匹配的是空串
        }

        if(s[sptr] == p[pptr] || (p[pptr] == '.' && s[sptr] != '\0'))
            return matchCore(s, p, sptr + 1, pptr + 1);

        return false;
    }
};